// 合并两个升序链表
function mergeTwoLists(l1,l2){
    const dummyHead={};
    let current=dummyHead;//定义当前节点 用于添加后继
    // 遍历两个链表 并比较两个链表 直到某个链表被遍历完成
    while(l1 !==null && l2 !==null){
        // 比较两个链表的值
        if(l1.val<l2.val){
            current.next=l1;//把小的值添加在后面
            current=current.next;//当前节点指向下一个
            l1=l1.next;//l1也指向下一个
        }else{
            current.next=l2;
            current=current.next;
            l2=l2.next;
        }

        // 当某个链表被遍历完 就将另一个剩余的未遍历数据添加在current后面
        if(l1===null){
            current.next=l2;
        }else{
            current.next=l1;
        }

        // 返回头节点
        return dummyHead.next;
    }
}

/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
 var mergeKLists = function(lists) {
    if(lists.length===0) return null;
    if(lists.length===1) return lists[0];
    if(lists.length===2){
        mergeTwoLists(lists[0],lists[1]);
    }

    // 分治
    // 进行分
    const mid=lists.length >> 1;
    const l1=[]; 
    for(let i=0;i<mid;i++){
        l1[i]=lists[i];
    }

    const l2=[];
    for(let i=mid,j=0;i<lists.length;i++,j++){
        l2[j]=lists[i];
    }

    // 递归 归并 进行治
    return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));
};

// let mid = 2 >> 1;
// console.log(mid);